Regular Languages

A Formal Languages that can be recognized by a finite automaton.

A language is regular if a finite automaton exists that recognizes the language.

Operations

Union: L_1 \cap L_2 = \{ x | (x \in L_1 )\lor (x \in L_2) \}
Concatenation: L_1 \cdot L_2 = L_1 L_2 = \{ xy | (x \in L_1) \land (y \in L_2) \}

Regular Expressions

A word R is a regular expression of an alphabet \Sigma if it's part of the following and \{\epsilon, \emptyset, | , \cdot, *, (, ) \} \cup \Sigma = \emptyset:

a (a\in\Sigma)
\epsilon
\emptyset
(R_1 | R_2)
R_1 \cdot R_2
R_1^*
(R_1)